1. Field of the Invention
The present invention relates to electronic circuits, and more specifically to a circuit and method for performing multiplication with accumulation in a Galois Field.
2. Description of Related Art
GF(2k) is the field of polynomials of degree kxe2x88x921 at the most with coefficients over {0,1}. Galois Fields are examples of finite element sets on which mathematical operations are defined differently. The Galois Field GF(2k) is a field which comprises k elements, with k=2k. A representation of this field is the polynomial representation. All the elements can be expressed in the form of a polynomial of degree kxe2x88x921: P(x)=akxe2x88x921xkxe2x88x921+akxe2x88x922xkxe2x88x922+ . . . a2x2+a1x+a0, with ai being a coefficient belonging to GF(2), and thus equal to either xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d. Consequently, each element can be assimilated to a number coded on k bits. This causes the calculations performed on the different elements to correspond to calculations performed on polynomials reduced using an irreducible polynomial of degree k.
Galois Fields can be used in digital transmissions to produce error correction codes or as mathematical structures serving as a support for implementing cryptographic systems. An example of encryption codes is the elliptic curve encryption. This type of encryption uses binary numbers coded on a large number of bits (typically 150 to 200 bits). The calculation devices used at present are classical processors, and in some cases are coupled to dedicated circuits. If a conventional processor is used, the calculation time is difficult to optimize. On the other hand, the use of dedicated circuits is more cumbersome and consumes more energy.
With Galois Fields, the calculations performed on numbers coded on k bits representing the elements of the field are carried out differently from usual addition and multiplication operations. Thus, the addition of two elements is carried out bit by bit using an exclusive OR logic circuit. A subtraction is carried in an identical manner as for an addition. A multiplication is performed in two stages: in a first stage a multiplication similar to the multiplication of two polynomials is performed, then in a second stage a reduction using an irreducible polynomial of degree k is performed.
Another operation frequently used in a Galois Field is a xe2x80x9cmultiplication with accumulationxe2x80x9d, which is denoted as Xmac. This operation, which calls for three items of data A, B and C, is defined as follows: Xmac(A,B,C)=Axc3x97B+C, where the symbol xe2x80x9cxxe2x80x9d denotes multiplication in the sense of the arithmetic of polynomials with coefficients on GF(2), and where the symbol xe2x80x9c+xe2x80x9d denotes addition in the sense of the arithmetic of a Galois Field.
Conventionally, the data A, B and C are coded on a same number of bits. Thus, if A and B are coded on n bits, an electronic circuit for carrying out the multiplication in the sense of the arithmetic of a Galois Field would comprise n accumulation latches, n adders, and so on. Accordingly, the size of circuits suitable for carrying out operations in a Galois Field depends directly on the size (i.e., the number of bits) of the numbers that involved in the different operations.
FIG. 1 is a block diagram showing a conventional circuit for performing multiplication operation with accumulation in a Galois Field. As mentioned above, three items of data A, B and C are used in a multiplication operation with accumulation. The first data A is stored in a first input register Areg, the second data B is stored in a second input register Breg, and the third data C is stored in a third input register Creg. The data A, B, and C have a size of 2 n bits. The first, second, and third input registers Areg, Breg, and Creg are preferably registers capable of containing 2 n bits. They can, however, have a different size, provided their size is sufficient to contain the data A, B, and C. The different registers can belong to a common memory unit or to separate memory units.
A circuit 10 for multiplication in a Galois Field receives the data A and B, which are respectively conveyed by a first data bus 12 and by a second data bus 14 from the input registers Areg and Breg. The circuit 10 for multiplication in a Galois Field performs a multiplication, in accordance with the arithmetic of a Galois Field, of the first data A and the second data B. The result of this multiplication, which is output by the multiplication circuit 10, is a number coded on 4 n bits. This result is sent to a logic circuit 18 by a third data bus 16. The logic circuit 18 carries out the addition, in accordance with the arithmetic of a Galois Field, of the result of the multiplication in the Galois Field and the third data C stored in third register Creg. In particular, the third data bus 20 sends the 2 n bits coding the number C to the logic circuit 18. Generally, the logic circuit 18 is a two input exclusive OR (ex-OR) gate.
The result of the addition, in the sense of the arithmetic of a Galois Field, performed by the logic circuit 18 is a number coded on 4 n bits. The 2 n lowest weight bits (i.e., least significant bits) of the result of the addition operation are stored in a first output register LSW (less significant word) and the 2 n highest weight bits (i.e., most significant bits) of the result of the operation are stored in a second output register MSW (most significant word).
As mentioned above, the size of the circuit 10 for multiplication in a Galois Field depends directly on the size of the numbers which must be multiplied. It is common, for example in encryption operations of the elliptical curve type, to have to perform multiplications of numbers coded on 32 bits. The size of the multiplication circuit 10 is then quite considerable and it becomes too costly to implement because of the size of the required multiplication circuit.
In view of these drawbacks, it is an object of the present invention to overcome the above-mentioned drawbacks and to provide a method for performing multiplication with accumulation in a Galois Field using a multiplication circuit that is not extremely large, and therefore not overly costly. A specific chain of successive operations is performed which makes it possible to replace multiplication between two numbers of 2 n bits by two multiplications between one number of 2 n bits and one number of n bits. Thus, The multiplication circuit required to implement the operation (i.e., which must perform multiplications between a number of 2 n bits and a number of n bits) is reduced in size by approximately two. More specifically, in the circuit for performing such a multiplication, the 2 n accumulation latches, 2 n adders, and so on are replaced by n accumulation latches and n adders.
One embodiment of the present invention provides a method is provided for performing multiplication with accumulation in a Galois Field on a first data, a second data, and a third data, with each of the data being coded on 2 n bits. According to the method, a first multiplication, in the sense of the arithmetic of a Galois Field, is performed on the first data and the n lowest weight bits of the second data to produce a first intermediate result coded on 3 n bits, and a first addition, in the sense of the arithmetic of a Galois Field, is performed on the third data and the first intermediate result to produce a second intermediate result on 3 n bits. A second multiplication, in the sense of the arithmetic of a Galois Field, is performed on the first data and the n highest weight bits of the second data to produce a third intermediate result on 3 n bits, and a second addition, in the sense of the arithmetic of Galois Field, is performed on the 2 n highest weight bits of the second intermediate result and the third intermediate result to produce a fourth intermediate result coded on 3 n bits. In a preferred embodiment, the 2 n highest weight bits of the second intermediate result are stored in an intermediate register and the n lowest weight bits of the second intermediate result in an output register, and the n lowest weight bits stored in the output register are shifted to the lowest weight bits of the output register.